package sample.xiaosong.greedyalgorithms;

import java.util.PriorityQueue;

/**
 * 金条分割问题:
 *
 * 一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金 条，不管切成长度多大的两半，都要花费20个铜板。
 * 一群人想整分整块金条，怎么分最省铜板? 例如,给定数组{10,20,30}，代表一共三个人，整块金条长度为10+20+30=60。
 * 金条要分成10,20,30三个部分。 如果先把长度60的金条分成10和50，花费60； 再把长度50的金条分成20和30，花费50；一共花费110铜板。
 * 但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20， 花费30；一共花费90铜板。
 * 输入一个数组，返回分割的最小代价。
 */
public class LessMoneySplitGold {

    /**
     * 贪心算法的入手角度：每一次切分时，都是对最小结果的切分
     *
     * 理解贪心算法的角度，我们可以先假设金条已经按照最好方案切分好。
     * 首先取出最小的两块，相加得到花费最小的一次切分，然后将结果加入队列，队列会自动按从小到大排序
     * 随后循环此过程，直到队列里的个数小于2，得到的结果即是最小结果
     * @param array 数组
     * @return 最小切分值
     */
    public static int getLessMoney(int[] array) {
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for (int i : array) {
            queue.add(i);
        }
        int sum = 0;
        int current;
        while (queue.size() > 1) {
            current = queue.poll();
            if (!queue.isEmpty()) {
             current += queue.poll();
            } else {
                break;
            }
            sum += current;
            queue.add(current);
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] arr = { 6, 7, 8, 9 };
        System.out.println(getLessMoney(arr));

        int[] arr1 = {10, 20, 30};
        System.out.println(getLessMoney(arr1));

        int[] arr2 = {15, 35, 30, 20};
        System.out.println(getLessMoney(arr2));
    }
}
